/**
 * 原理：遍历数组，将搜索当前索引位置及之后的元素中的最小值，找到之后和当前索引位置的元素交换位置。
   简单来说就是：选择剩余数组中最小的值放到有序数组末尾。
   技巧：将数组元素交换过程和寻找剩余数组中最小元素的过程抽离成独立方法可以使整个过程更加清晰。

   时间复杂度：最好O(n*n),最坏O(n*n)
   空间：O(1)
   不稳定排序

   怎么看是否稳定：
    如果大小相同的两个值在排序之前和排序之后的先后顺序不变，那就可以说这种排序算法是稳定的。

    选择排序：原理是从第一个元素开始，在之后的所有元素中选择一个最小的交换过来。如果说原序列中第一个元素和第二个元素相等，第三个元素是个最小值，
    经过选择会把第一个元素和第三个元素交换，这时第二个元素就跑到前面去了。如：3,3,1序列，经过选择排序会变成1,3,3。所以是不稳定的排序。
 * @param {*} arr 
 * @returns 排序后的数组
 */
function selectionSort(arr) {
  let _arr = [...arr];
  if (_arr.length < 2) return _arr;
  let len = _arr.length;

  // 给定区间，查找区间内最小值的index
  function findMinIndex(start, end) {
    let minIndex = start;
    let minVal = _arr[start];

    for (let i = start; i <= end; i++) {
      if (_arr[i] < minVal) {
        minVal = _arr[i];
        minIndex = i;
      }
    }

    return minIndex;
  }

  // 利用数组解构交换两个值
  function swap(i, j) {
    if (1 === j) return;
    [_arr[i], _arr[j]] = [_arr[j], _arr[i]];
  }

  // 遍历数组，逐个替换
  for (let i = 0; i < len; i++) {
    let minIndex = findMinIndex(i, len - 1);
    swap(i, minIndex);
  }

  return _arr;
}

// egg:

const arr = [1, 3, 5, 4, 6, 8, 2, 7];

console.log("[ arr ] >", selectionSort(arr));
